package model.parseTree;

import model.searchers.ISearcher;
import model.searchers.URLList;

/**
 * Class SyntaxTree maintains a binary syntax tree for a given String query.
 * It consists of different kinds of nodes of type SearchNode, which should 
 * themselves be able to evaluate their child nodes.
 * The String may contain search words, parentheses and boolean operators AND, OR. 
 */
public class SyntaxTree {
	private SearchNode rootNode;
	private static final String[] operators = { "OR", "AND" };
	
	/**
	 * Constructor of SyntaxTree. Grows a syntax tree from the given query
	 * 
	 * @param query		a String from which to grow a syntax tree
	 */
	public SyntaxTree(String query) {
		growTree(query);
	}

	/**
	 * Returns the rootnode of the syntax tree
	 * 
	 * @return the rootnode
	 */
	public SearchNode getRootNode() {
		return rootNode;
	}

	/**
	 * Builds the tree structure from given query
	 * 
	 * @param query		string to grow tree from
	 */
	public void growTree(String query) {
		if (query == null || !oddNumberOfParens(query)) {
			return;
		}
		boolean operatorFound = false;
		int parCounter = 0; //keeps track of parentheses. Start "(" adds 1, end ")" subtracts 1
		int parLevel = 0;

		//splits the query into an array of separate words
		String[] splitted = query.split("\\s");
		
		//a wordnode is created if the query contains exactly one word
		if (splitted.length == 1 ) {
			rootNode = makeNode(splitted[0].replaceAll("\\(", "").replaceAll("\\)", ""), null, null);
		} 
		//in this case, someone searched for more than one word, but did not put in any operators. Return with no results.
		else if (!SyntaxTree.anyOperators(query)) {	
			 return;
		}
		else
		//if the query contains more than one word, we search for boolean operators
		{
			while (!operatorFound) {
			int opIndex = 0; //first operator to look for is OR, since it has lowest precedence
			while (opIndex < operators.length && !operatorFound) {
				int wordIndex = 0;
				while (wordIndex < splitted.length && !operatorFound) {
					
					if (parensInsideWord(splitted[wordIndex])) return;
					/*parCounter is increased by number of left parentheses in
					beginning of word and decreased by the number of right parentheses in the
					end of the word. We assume that left parentheses are only in beginning of
					word and right parentheses are only in the end of the word
					*/
					parCounter += splitted[wordIndex].lastIndexOf("(") + 1;
					int endPar = splitted[wordIndex].indexOf(")");
					if (endPar != -1) {
						parCounter -= splitted[wordIndex].length() - endPar;
					}
					if (splitted[wordIndex].equals(operators[opIndex])
							&& parCounter == parLevel) {
						operatorFound = true;
						//make sure that there is at least a word before and a word after the operator-node and that
						//there are no operators next to each other. Return with no results if so.
						if ( wordIndex - 1 >= 0 && wordIndex + 1 < splitted.length 
								&& (SyntaxTree.anyOperators(splitted[wordIndex+1]) || SyntaxTree.anyOperators(splitted[wordIndex-1]))) {
								return;
							}						
							 else {
								//when an operator is found, a subtree is created 
								rootNode = makeNode(
										splitted[wordIndex],
										getArray(splitted, wordIndex, parLevel),
										getRestOfArray(splitted, wordIndex + 1,
												parLevel));
							}
						}
					wordIndex++;
				}
				opIndex++;
			}
			parLevel++;
		}
		}
	}

	/**
	 * Creates a node in the tree and thereby creating its subtrees from left and right subqueries
	 * 
	 * @param value 	String value of the search node, which can be AND, OR or a word	
	 * @param left 		left subquery
	 * @param right		right subquery
	 * @return			a new node in the syntax tree
	 */
	public SearchNode makeNode(String value, String left, String right) {
		SearchNode node = null;
		if (value.equals("OR")) {
			node = new OrNode(new SyntaxTree(left).getRootNode(),
					new SyntaxTree(right).getRootNode());
		} else if (value.equals("AND")) {
			node = new AndNode(new SyntaxTree(left).getRootNode(),
					new SyntaxTree(right).getRootNode());
		} else {
			node = new WordNode(value);
		}
		return node;
	}

	/**
	 * Create a URLList of results of a search for the query of the syntax tree, performed by a given searcher
	 * @param searcher 		the searcher to search for the query
	 * @return 				a list of results and occurrences on each URL
	 */
	public URLList readTree(ISearcher searcher) {
		if (rootNode != null)
		return rootNode.getResult(searcher);
		else return null;
	}

	/**
	 * Creates a string containing all words that are placed on and after a given index in a String array.
	 * (Helper method for growTree)
	 * 
	 * @param stringArray	the array to get words from
	 * @param index			the index of first word to get out of array
	 * @param parLevel 		the current accepted level of parentheses 
	 * @return a String containing all words placed after index
	 */
	private String getRestOfArray(String[] stringArray, int index, int parLevel) {
		int alength = stringArray.length;
		String s = "";
		for (int i = index; i < alength - 1; i++) // evt length -1
		{
			if (!stringArray.equals("") || !stringArray.equals(" "))
				s += stringArray[i] + " ";
		}
		// removes already considered parentheses from end of query
		String lastWord = stringArray[alength - 1];
		s += lastWord.substring(0, lastWord.length() - parLevel);
		
		return s;
	}

	/**
	 * Creates a string containing all words that are placed strictly before a given index in a String array.
	 * (Helper method for growTree)
	 * 
	 * @param stringArray 	the array to get words from
	 * @param index 		the index of first word NOT to get out of array
	 * @param parLevel 		the current accepted level of parentheses 
	 * @return 				a String containing all words placed before index
	 */
	private String getArray(String[] stringArray, int index, int parLevel) {
		// removes already considered parentheses from beginning of query
		String s = stringArray[0].substring(parLevel);

		for (int i = 1; i < index; i++) {
			if (!stringArray.equals("") || !stringArray.equals(" "))
				s += " " + stringArray[i];
		}
		return s;
	}

	/**
	 * Checks if there is any operator (AND/OR) in a given String
	 * @param s	String to check for operators
	 * @return	true if an operator is found, else false
	 */
	public static boolean  anyOperators(String s) {
		String[] split = s.split("\\s");
		for (int i = 0; i < split.length; i++) {
			for (int j = 0; j < operators.length; j++) {
				if (split[i].equals(operators[j])) {
					return true;
				} 
			}
		}
		return false;
	}
	
	/**
	 * Check if there is an odd number of parentheses in a given query
	 * 
	 * @param query	String to check for odd nb. of parentheses
	 * @return	true if there is an odd nb. of parentheses in the query, else false
	 */
	private boolean oddNumberOfParens(String query) {
		int parensCounter = 0;
		for (int i = 0; i < query.length(); i++) {
			if (query.charAt(i) == '(') parensCounter++;
			if (query.charAt(i) == ')') parensCounter--;
		}
		return (parensCounter == 0);
	}
	
	/**
	 * Checks if there is any parentheses in the "middle" of a word
	 * 
	 * @param query	String to check for parentheses
	 * @return	true if there are, else false
	 */
	private boolean parensInsideWord(String query) {
		
		int indexLeft=query.indexOf('(');
		int indexRight=query.indexOf(')');
		if (indexLeft < 0 || indexRight < 0) {			
			return false;
		}
		int indexOther;
		for (int i = 0; i < query.length(); i++) {
			if (query.charAt(i) == '('){
				indexLeft = i;
			} else
			
			if (query.charAt(i) == ')') {
					indexRight = i;
			} 
			else
			{
			indexOther = i;
			if (indexOther < indexLeft || indexOther > indexRight) {
				return true;
			}
			
			}

		}
		
		return false;	
	}
	
	
}
